package simple;


import java.util.Deque;
import java.util.LinkedList;

/**
 * @author gree
 */
public class LongestValidParentheses {
    public static long solution(String s){
         int maxnas = 0;
         int[] dp = new int[s.length()];
         for(int i =1;i<s.length();i++){
             if(s.charAt(i) == ')'){
                 if(s.charAt(i-1) == '('){
                     dp[i]  = (i>=2 ? dp[i-2]:0) +2;
                 }else if(i-dp[i-1] > 0 && s.charAt(i-dp[i-1] -1) == '('){
                     dp[i] = dp[i-1] + ((i-dp[i-1]) >= 2 ? dp[i-dp[i-1] -2]: 0)+2;
                 }
                 maxnas = Math.max(maxnas,dp[i]);
             }
         }
         return maxnas;
    }

    public static  long solution1(String s){
        int maxnas = 0;
        Deque<Integer> stack = new LinkedList<>();
        stack.push(-1);
        for (int i = 0;i<s.length();i++){
            if(s.charAt(i) == ')'){
                stack.pop();
                if(stack.isEmpty()){
                    stack.push(i);
                }else{
                    maxnas = Math.max(maxnas,i-stack.peek());
                }
            }else {
                stack.push(i);
            }
        }
        return maxnas;
    }


    public static void main(String[] args) {
       String str = "(()()(";
        System.out.println(solution1(str));
    }
}
